Méthode de type off-policy avec approximations

9. Méthodes Emphatic-TD

9.1. Introduction aux méthodes Emphatic-TD

Passons maintenant à la seconde méthode très utilisée dans le cadre de l'apprentissage hors-ligne en utilisant des approximations de fonctions. Mais tout d'abord, afin de mieux comprendre la structure de ces méthodes, faisons un petit retour sur l'analyse de la stabilité des méthodes TD.

Étude de la stabilité des méthodes TD on-policy

Dans les méthodes TD, le poids est mis à jour de la manière suivante:

$${\textbf{w}_{t + 1}} = {\textbf{w}_t} + \alpha \left[ {{R_{t + 1}} + \gamma \hat v\left( {{S_{t + 1}},{\textbf{w}_t}} \right) - \hat v\left( {{S_t},{\textbf{w}_t}} \right)} \right]\nabla \hat v\left( {{S_t},{\textbf{w}_t}} \right)$$

avec:

$$\hat v\left( {{S_t},{\textbf{w}_t}} \right) = {\textbf{w}_t}^T{\textbf{x}_t}\left( s \right)$$

Dans le cas où les approximations sont linéaires on a également : $\nabla \hat v\left( {{S_t},{\textbf{w}_t}} \right) = {\textbf{x}_t}\left( s \right)$

L'équation de mise à jour du poids devient donc (en utilisant la notation abrégée ${\textbf{x}_t} = {\textbf{x}_t}\left( s \right))$:

$${\textbf{w}_{t + 1}} = {\textbf{w}_t} + \alpha \left[ {{R_{t + 1}} + \gamma {\textbf{w}_t}^T{\textbf{x}_{t + 1}} - {\textbf{w}_t}^T{\textbf{x}_t}} \right]{\textbf{x}_t}$$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \textbf{ = }{\textbf{w}_t} + \alpha \left[ {{R_{t + 1}}{\textbf{x}_t} + \gamma {\textbf{w}_t}^T{\textbf{x}_{t + 1}}{\textbf{x}_t} - {\textbf{w}_t}^T{\textbf{x}_t}{\textbf{x}_t}} \right]$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \textbf{ = }{\textbf{w}_t} + \alpha \left[ {{R_{t + 1}}{\textbf{x}_t} + \gamma {\textbf{x}_{t + 1}}^T{\textbf{x}_t}{\textbf{w}_t} - {\textbf{x}_t}{\textbf{x}_t}^T{\textbf{w}_t}} \right]$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \textbf{ = }{\textbf{w}_t} + \alpha \left[ {{R_{t + 1}}{\textbf{x}_t} - {\textbf{x}_t}\left( {{\textbf{x}_t}^T - \gamma {\textbf{x}_{t + 1}}^T} \right){\textbf{w}_t}} \right]$

$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = {\textbf{w}_t} + \alpha \left[ {{R_{t + 1}}{\textbf{x}_t} - {\textbf{x}_t}{{\left( {{\textbf{x}_t} - \gamma {\textbf{x}_{t + 1}}} \right)}^T}{\textbf{w}_t}} \right]$

Lorsque l'algorithme est établi, alors pour un poids donné $\textbf{w}_t$, l'espérance de la nouvelle valeur à l'instant suivant peut s'écrire:

$$E\left[ {{\textbf{w}_{t + 1}}|{\textbf{w}_t}} \right] = {\textbf{w}_t} + \alpha \left( {b - A{\textbf{w}_t}} \right)$$

avec $b = E\left[ {{R_{t + 1}}{\textbf{x}_t}} \right]$ et $A = E\left[ {{\textbf{x}_t}{{\left( {{\textbf{x}_t} - \gamma {\textbf{x}_{t + 1}}} \right)}^T}} \right]$.

L'espérance précédente peut s'écrire également de la manière suivante:

$$E\left[ {{\textbf{w}_{t + 1}}|{\textbf{w}_t}} \right] = \left( {I - \alpha A} \right){\textbf{w}_t} + \alpha b$$

On remarque que le vecteur poids $\textbf{w}_t$ n'est multiplié que par la matrice A. C'est donc uniquement cette matrice qui est importante pour la convergence de l'algorithme. Prenons le cas particulier où cette matrice est diagonale:

• Dans ce cas, si les valeurs de la diagonale sont négatives, alors le facteur $(I-\alpha A)$ sera plus grand que 1, et donc les composantes du vecteur poids vont augmenter et l'algorithme va diverger.
• Si par contre les valeurs de la diagonale sont positives, alors le taux d'apprentissage $\alpha$ peut être choisi inférieur à 1 de manière à ce que le facteur $(I-\alpha A)$ ait des valeurs sur la diagonale comprises entre 0 et 1. Dans ce cas, l'algorithme converge.

Dans le cas de l'algorithme TD(0) avec des approximations linéaires, la matrice $A$ peut s'écrire:

$$A = E\left[ {{\textbf{x}_t}{{\left( {{\textbf{x}_t} - \gamma {\textbf{x}_{t + 1}}} \right)}^T}} \right]$$

$$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \sum\limits_a {\pi \left( {a|s} \right)} \sum\limits_{r,s'} {p\left( {r,s'|s,a} \right)\textbf{x}\left( s \right)} {\left[ {\textbf{x}\left( s \right) - \gamma \textbf{x}\left( {s'} \right)} \right]^T}$$

$$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \sum\limits_{s'} {p\left( {s'|s} \right)\textbf{x}\left( s \right)} {\left[ {\textbf{x}\left( s \right) - \gamma \textbf{x}\left( {s'} \right)} \right]^T}$$

$$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \textbf{x}\left( s \right){\left[ {\textbf{x}\left( s \right) - \gamma \sum\limits_{s'} {p\left( {s'|s} \right)} \textbf{x}\left( {s'} \right)} \right]^T}$$

$$ = {X^T}D\left( {I - \gamma P} \right)X$$

où $μ(s)$ est la distribution stationnaire sous la stratégie $\pi$, $p(s'|s)$ est la probabilité de transition des états $s$ vers $s'$ sous la stratégie $\pi$, P est la matrice de dimension $|S| \times |S|$ de ces probabilités, $D$ est la matrice avec les valeurs des distributions sur les diagonales, et $X$ est la matrice de dimension $|S| \times d$ avec les vecteurs caractéristiques $\textbf{x}(s)$ sur ses lignes. Il est clair que le facteur $D(I-\gamma P)$ est la clé de la stabilité de la convergence de l'algorithme.

On peut en déduire que la stabilité de l'algorithme dépend de la distribution des états en-ligne $\mu_\pi$ sous la stratégie cible $\pi$ et de la probabilité des transitions $p(s'|s)$ sous la stratégie cible $\pi$.

Principe pour assurer la stabilité des méthodes TD(0) off-policy

Dans le cadre de l'apprentissage hors-ligne, les probabilités de transitions $p(s'|s)$ sous la stratégies cible $\pi$ sont évaluées à partir de celles obtenues à partir de la stratégie d'exploitation $b$. Cela se fait à l'aide du ratio d’échantillonnage préférentiel. La stabilité de l'algorithme est donc assurée concernant les probabilités de transitions.

Par contre, les distributions des états utilisées continuent d'être celles de la stratégie d'exploitation, et non celle de la stratégie cible. C'est là que se pose le problème d'équilibre entre méthode en-ligne et hors-ligne.

L'idée qui vient à l'esprit est donc de chercher à pondérer les valeurs des distributions pour les rendre compatibles avec la stratégie cible, en mettant certaines valeurs en avant par rapport à d'autres. Cela apporterait un équilibre et donc une stabilité à l'algorithme off-policy. C'est l'idée sous-jacente des méthodes Emphatic-TD (Emphatic signifie "insistant" en Anglais).

Algorithme Emphatic-TD

L'algorithme à un pas utilisé pour l'apprentissage de type épisodique est le suivant:

$\quad \quad \quad \quad \delta \left( t \right) = {R_{t + 1}} + \gamma \hat v\left( {{S_{t + 1}},{\textbf{w}_t}} \right) - \hat v\left( {{S_t},{\textbf{w}_t}} \right)$

$\quad \quad \quad \quad {\textbf{w}_{t + 1}} = {\textbf{w}_t} + \alpha {M_t}{\rho _t}{\delta _t}\nabla \hat v\left( {{S_t},{\textbf{w}_t}} \right)$

$\quad \quad \quad \quad {M_t} = \gamma {\rho _{t - 1}}{M_{t - 1}} + {I_t}$

$I_t$ est l'intérêt. Il indique le degré avec lequel on souhaite apporter de la valeur à évaluer l'état courant à l'instant $t$. Si on n'apporte aucun intérêt à cet état, alors la valeur de l'intérêt doit être nulle. Si on souhaite le prendre en compte complétement, alors elle doit valoir 1. Cette valeur est arbitraire et peut dépendre de l'environnement et d'autres paramètres.

$M_t$ est l'accent (emphasis) que l'on souhaite mettre sur la mise à jour du vecteur poids. Cette valeur est initialisée à $M_{t-1}=0$.